#include <bits/stdc++.h>
using namespace std;

/*
2099. 找到和最大的长度为 K 的子序列
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ，且这个子序列的 和最大 。

请你返回 任意 一个长度为 k 的整数子序列。

子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。

 

示例 1：

输入：nums = [2,1,3,3], k = 2
输出：[3,3]
解释：
子序列有最大和：3 + 3 = 6 。
示例 2：

输入：nums = [-1,-2,3,4], k = 3
输出：[-1,3,4]
解释：
子序列有最大和：-1 + 3 + 4 = 6 。
示例 3：

输入：nums = [3,4,3,3], k = 2
输出：[3,4]
解释：
子序列有最大和：3 + 4 = 7 。
另一个可行的子序列为 [4, 3] 。
 

提示：

1 <= nums.length <= 1000
-105 <= nums[i] <= 105
1 <= k <= nums.length
*/

// 法一
class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        int n = nums.size();
        vector<pair<int, int>> idxNums;     // 键值对存储

        // 原始数组的遍历 进辅助容器
        for (int i = 0; i < n; i++) {
            idxNums.emplace_back(i, nums[i]);
        }

        // sort DESC
        sort(idxNums.begin(), idxNums.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        });
        // 前k个  原始索引ACS  子序列和原始的一致
        sort(idxNums.begin(), idxNums.begin() + k, [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first < b.first;
        });

        // 前k个的遍历结果进结果容器
        vector<int> ans;
        for (int i = 0; i < k; i++) ans.push_back(idxNums[i].second);

        return ans;
    }
};

// 法二
class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        vector<int> res;  // 存储最终结果的子序列
        vector<int> _nums_2 = nums;  // 复制原数组用于排序（命名建议改为sortedNums更清晰）
        
        // 步骤1：对复制的数组进行升序排序，便于后续筛选最小的n-k个元素
        sort(_nums_2.begin(), _nums_2.end());
        
        // 计算需要排除的元素数量（原数组长度 - 需要的子序列长度）
        int _lose_num = nums.size() - k;
        
        // 使用哈希表记录需要排除的元素及其出现次数
        unordered_map<int, int> number_;
        
        // 步骤2：将排序后前n-k个最小元素存入哈希表（这些元素不进入结果）
        for(int i = 0; i < _lose_num; i++) {
            number_[_nums_2[i]]++;  // 统计待排除元素的频率
        }
        
        // 步骤3：遍历原数组构建结果
        for(int i = 0; i < nums.size(); i++) {
            auto it = number_.find(nums[i]);
            
            // 当前元素存在于待排除列表时的处理
            if(it != number_.end()) {
                // 如果该元素仍需排除（计数器>0）
                if(it->second != 0) {
                    it->second--;  // 减少排除计数器
                } 
                // 否则加入结果（说明已超过需要排除的次数）
                else {
                    res.push_back(nums[i]);
                }
            } 
            // 当前元素不在排除列表，直接加入结果
            else {
                res.push_back(nums[i]);
            }
        }
        
        return res;  // 返回长度为k的最大和子序列（保持原顺序）
    }
};